import datastructure.linklist.ListNode;

/**
 * @Author ZhangCuirong
 * @Date 2025/8/21 21:10
 * @description:
 */
public class Solution86 {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode slow = dummy;  // 指向小于x区域的最后一个节点
        ListNode fast = dummy;  // 遍历指针

        while (fast.next != null) {
            // 只有当当前节点需要移动且不是已经在正确位置时才进行交换
            if (fast.next.val < x) {
                // 避免对已经在小于区域的节点重复操作（关键修正）
                if (slow != fast) {
                    ListNode temp = fast.next;
                    fast.next = fast.next.next;  // 移除要移动的节点
                    temp.next = slow.next;       // 插入到slow后面
                    slow.next = temp;
                } else {
                    // 当slow和fast指向同一节点时，只需移动fast（说明当前节点已在正确位置）
                    fast = fast.next;
                }
                slow = slow.next;  // 小于区域扩展
            } else {
                // 不小于x的节点，只需移动fast指针
                fast = fast.next;
            }
        }
        // 移除原代码中错误的尾节点判断
        return dummy.next;
    }

    public ListNode partition2(ListNode head, int x) {
        ListNode smallDummy = new ListNode(-1);
        ListNode largeDummy = new ListNode(-1);
        ListNode small = smallDummy;
        ListNode large = largeDummy;
        ListNode p = head;

        while (p != null) {
            if (p.val < x) {
                small.next = p;
                small = small.next;
            } else {
                large.next = p;
                large = large.next;
            }
            p = p.next;
        }
        small.next = largeDummy.next;
        large.next = null;//不加链表有环
        return smallDummy.next;

    }

    public static void main(String[] args) {
        int[] nums = {1, 4, 3, 2, 5, 2};
        ListNode head = ListNode.arrayToList(nums);
        Solution86 solution = new Solution86();
//        datastructure.linklist.ListNode newHead = solution.partition(head, 3);
//        datastructure.linklist.ListNode.printList(newHead);
        ListNode newHead2 = solution.partition2(head, 3);
        ListNode.printList(newHead2);
    }
}
